package org.example.myleet.rosalind.perm;

public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
//        solution.findAllPermutationForN(3);
        solution.findAllPermutationForN(6);
    }

    public void findAllPermutationForN(int n) {
        int[] numbers = new int[n];
        for (int i = 1; i <= n; ++i) {
            numbers[i - 1] = i;
        }
        int count = 0;
        int[] nextPermutation = nextPermutation(numbers);
        ++count;
        while (hasNext(numbers, nextPermutation)) {
            printPermutation(numbers);
            numbers = nextPermutation;
            nextPermutation = nextPermutation(numbers);
            ++count;
        }
        printPermutation(numbers);
        System.out.println(count);
    }

    private boolean hasNext(int[] prevNumbers, int[] numbers) {
        for (int i = 0; i < prevNumbers.length; ++i) {
            if (prevNumbers[i] != numbers[i]) {
                return true;
            }
        }
        return false;
    }

    private int[] nextPermutation(int[] input) {
        int n = input.length;
        //这里对input做了拷贝，操作过程不影响input
        int[] output = new int[n];
        System.arraycopy(input, 0, output, 0, n);
        if (n < 2) {
            //少于2个字符长度的没有下一个字典序可言
            return output;
        }
        //1、从字符串结尾开始向头部扫描，找到第一个出现降序的字符，满足numbers[i] < numbers[j]，标记j位置
        //解析：能找到这样的位置，说明还存在存在更大的字典序
        int j = n - 1, i = j - 1;
        while (i >= 0) {
            if (output[i] < output[j]) {
                break;
            }
            --i;
            --j;
        }
        if (i < 0) {
            //已经是最大字典序，结束
            return output;
        }
        //2、从j位置开始往numbers结尾查找，找到numbers[i]后面最后一个比numbers[i]大的数numbers[j]
        //解析：numbers[j]是i位置之后刚刚好比numbers[i]大的数，这样选numbers[j]的原因是下一个字典序是离现在的字典序最近的
        for (int k = j; k < n; ++k) {
            if (output[i] < output[k]) {
                j = k;
            }
        }
        //3、将i和j位置的字符对调
        //解析：此时numbers[j]被放到i位置，这样字典序就已经比input大很多了
        int t = output[j];
        output[j] = output[i];
        output[i] = t;
        //4、最后将(i+1)位置到结尾范围的字符翻转，即可得到下一个字典序结果
        //解析：注意到numbers[i+1]、numbers[i+2]...numbers[n-1]的排列是单调递减的，此段范围内字典序最大，通过翻转之后可以变成最小字典序
        //以上四步完成后即可得到最接近input的下一个字典序，因为numbers[j]是刚刚好比numbers[i]大，且i位置后的序列变成最小字典序
        int l = i + 1, r = n - 1;
        while (l < r) {
            t = output[l];
            output[l] = output[r];
            output[r] = t;
            ++l;
            --r;
        }
        return output;
    }

    private void printPermutation(int[] numbers) {
        StringBuilder output = new StringBuilder();
        for (int number : numbers) {
            output.append(number).append(' ');
        }
        output.deleteCharAt(output.length() - 1);
        System.out.println(output);
    }
}
